/**
 * Copyright (c) 2017-2024 Nop Platform. All rights reserved.
 * Author: canonical_entropy@163.com
 * Blog:   https://www.zhihu.com/people/canonical-entropy
 * Gitee:  https://gitee.com/canonical-entropy/nop-entropy
 * Github: https://github.com/entropy-cloud/nop-entropy
 */
package com.gitee.wsl.text

import kotlinx.io.IOException
import kotlin.math.min

class StringTrie<T> {
    enum class AddType {
        // 一个key仅允许一个value, 如果key出现重复, 则抛出异常
        UNIQUE,

        // 保留key对应的第一个value, 再加入的value被忽略
        KEEP_FIRST,

        // 保留key对应的最后一个value, 后加入的value会取代此前加入的value
        KEEP_LAST
    }

    val roots: MutableList<TrieNode<T?>> = mutableListOf()

    class TrieNode<T>(
        var data: CharSequence,
        /**
         * 匹配本节点时对应的总的前缀长度，可以用于和key来比较来确定是前缀匹配还是整体匹配
         *
         * @return
         */
        val keyLength: Int,
        var `object`: T
    ) {
        val children: MutableList<TrieNode<T>> = ArrayList<TrieNode<T>>()

        fun addChild(child: TrieNode<T>) {
            children.add(child)
        }

        constructor(
             data: CharArray,
            /**
             * 匹配本节点时对应的总的前缀长度，可以用于和key来比较来确定是前缀匹配还是整体匹配
             *
             * @return
             */
             keyLength: Int,
             `object`: T
        ):this(data.concatToString(),keyLength, `object`)

        @Throws(IOException::class)
        fun dump(out: Appendable, indent: Int) {
            for (i in 0 until indent) {
                out.append("  ")
            }
            var i = 0
            val n = data.length
            while (i < n) {
                out.append(data[i])
                i++
            }
            val obj: T? = `object`
            if (obj != null) {
                out.append(':')
                out.append(obj.toString())
            }
            out.append("\n")

                for (child in children) {
                    child.dump(out, indent + 1)
                }

        }
    }

    fun add(str: CharSequence, value: T) {
        add(str, value, AddType.UNIQUE)
    }

    fun put(str: CharSequence, value: T) {
        add(str, value, AddType.KEEP_LAST)
    }

    fun putIfAbsent(str: CharSequence, value: T) {
        add(str, value, AddType.KEEP_FIRST)
    }

    fun add(str: CharSequence, value: T, addType: AddType?) {
        addToList(null, roots, str, 0, value, addType)
    }

    fun find(str: String): T? {
        val node = findNode(str, false)
        return node?.`object`
    }

    fun findWithPrefix(str: String): T? {
        val node = findNode(str, true)
        return node?.`object`
    }

    fun findNode(str: String, onlyPrefix: Boolean): TrieNode<T?>? {
        return findInList(roots, str, 0, onlyPrefix)
    }

    val isEmpty: Boolean
        get() = roots.isEmpty()

    fun findInList(
        list: List<TrieNode<T?>>?,
        str: String,
        startPos: Int,
        onlyPrefix: Boolean
    ): TrieNode<T?>? {
        val c = str[startPos]
        if (list == null) return null
        val n = list.size
        var i = 0
        while (i < n) {
            val node = list[i]
            val data = node.data
            if (data[0] == c) {
                val keyLen = node.keyLength
                if (keyLen > str.length) {
                    return null
                }

                if (!str.regionMatches(startPos + 1, data.toString(), 1,keyLen)) return null
                //if (!CharSequenceHelper.matchChars(str, startPos + 1, keyLen, data, 1)) return null

                if (keyLen == str.length) {
                    return node
                } else {
                    var find = findInList(node.children, str, keyLen, onlyPrefix)
                    if (onlyPrefix && find == null) find = node
                    return find
                }
            } else if (data[0] > c) {
                break
            }
            i++
        }
        return null
    }

    fun dump(out: Appendable) {
        try {
            out.append("trie=\n")
            for (root in roots) {
                root.dump(out, 0)
            }
        } catch (e: IOException) {
            throw e
        }
    }

    fun addToList(
        parent: TrieNode<T?>?,
        list: MutableList<TrieNode<T?>>,
        str: CharSequence,
        startPos: Int,
        value: T,
        addType: AddType?
    ) {
        val n = list.size
        val firstChar = str[startPos]
        val strLen = str.length
        var i = 0
        while (i < n) {
            val node = list[i]
            if (node.data[0] == firstChar) {
                val keyLen = node.keyLength
                val m = min(keyLen, strLen) - startPos
                var j = 1
                while (j < m) {
                    if (node.data[j] != str[j + startPos]) {
                        break
                    }
                    j++
                }
                if (j < m || keyLen > strLen) {
                    // 这里需要把节点拆分
                    /*val pre = CharArray(j)
                    java.lang.System.arraycopy(node.data, 0, pre, 0, pre.size)
                    val post = CharArray(node.data.length - j)
                    java.lang.System.arraycopy(node.data, j, post, 0, post.size)*/

                    val pre = node.data.subSequence(0,j)
                    val post = node.data.subSequence(j,node.data.length - j)

                    node.data = post
                    val preNode: TrieNode<T?>

                    val pos = startPos + j

                    if (j < m) {
                        preNode = TrieNode(pre, pos, null)
                        /*val postStr = CharArray(strLen - pos)
                        CharSequenceHelper.getChars(str, pos, strLen, postStr, 0)*/
                        val postStr =str.subSequence(pos,pos+strLen)

                        // 如果是在中间不匹配，则需要插入一个前缀节点，并产生一个新节点
                        val newNode = TrieNode<T?>(postStr, strLen, value)

                        if (newNode.data[0] > node.data[0]) {
                            preNode.addChild(node)
                            preNode.addChild(newNode)
                        } else {
                            preNode.addChild(newNode)
                            preNode.addChild(node)
                        }
                    } else {
                        // 如果整个str都已经匹配，则直接拆分出一个前缀节点，把值插入到前缀节点中即可
                        preNode = TrieNode(pre, pos, value)
                        preNode.addChild(node)
                    }

                    list[i] = preNode
                    return
                }
                if (keyLen < strLen) {
                    this.addToList(node, node.children, str, keyLen, value, addType)
                    return
                } else if (keyLen == strLen) {
                    when (addType) {
                        AddType.KEEP_FIRST -> {}
                        AddType.KEEP_LAST -> node.`object` = value
                        AddType.UNIQUE -> {
                            if (node.`object` == null) {
                                node.`object` = value
                                break
                            }
                            throw IllegalArgumentException("ERR_TEXT_TRIE_KEY_ALREADY_EXISTS")
                                /*.param(ARG_KEY, str)
                                .param(
                                    ARG_VALUE,
                                    value
                                )*/
                        }

                        else -> throw IllegalArgumentException("ERR_TEXT_TRIE_KEY_ALREADY_EXISTS")
                            /*.param(
                            ARG_KEY,
                            str
                        ).param(
                            ARG_VALUE,
                            value
                        )*/
                    }
                    return
                }
            } else if (node.data[0] > firstChar) {
                // child 是按照data[0]的顺序排列的
                //val data: CharArray = CharSequenceHelper.getChars(str, startPos, strLen)
                val data = str.subSequence(startPos,startPos+strLen)
                val newNode = TrieNode<T?>(data, strLen, value)
                list.add(i, newNode)
                return
            }
            i++
        }
        str.subSequence(startPos, startPos+strLen)
        //val data: CharArray = CharSequenceHelper.getChars(str, startPos, strLen)
        val data = str.subSequence(startPos,startPos+strLen)
        val newNode = TrieNode<T?>(data, strLen, value)
        list.add(newNode)
    }
}